
 /*
 * Universidad del Valle de Guatemala
 * CC2003 Algoritmos y Estructuras de Datos
 * Hoja de Trabajo No.3
 * SortLista.java
 */

/**
 *
 * @author Luis Antonio Siguenza Leiva
 * Carné: 10297
 * Fecha de creación: 07 de Agosto del 2011
 * Descripción: Clase principal que genera numeros aleatorios en una lista de 
 *              numeros enteros que los ordena utilizando los Sortings:
 *              Selection sort y Quick Sort
 */


//Importamos Librerias
import java.util.Random;
public class SortingLista {

    public static void main(String[] args){
    
    //Nueva lista de numeros enteros con "x" cantidad de elementos.
    int[] nums = new int[10];
    
    //Objeto de la clase Random
    Random aleatorio= new Random();
     
    //Almacena numeros enteros aleatorios en la lista
    for (int i = 0; i < nums.length; i++)
         nums[i]= aleatorio.nextInt();
         
    
    //Ordena de menor a mayor los elementos de la lista por SELECTIONSORT
    selectionSort(nums); // Sort them
    System.out.println("Ordenado por Selection Sort: ");
    for (int i = 0; i < nums.length; i++)
        //Imprime en pantalla la lista ya ordenada
        System.out.println(nums[i]);
    
    //Almacena nuevos numeros enteros aleatorios en la lista
    for (int i = 0; i < nums.length; i++)
         nums[i]= aleatorio.nextInt();
    
    //Ordena de menor a mayor los elementos de la lista por QUIKSORT
    System.out.println("Ordenado por Quik Sort: ");
    quikSort(nums,0,nums.length-1);
    for (int i = 0; i < nums.length; i++)
        //Imprime en pantalla la lista ya ordenada
        System.out.println(nums[i]);
  }  
    
  
    
  //******************************************************
  //*                   Metodo quikSort                  *     
  //******************************************************
  //*Pre: Lista de numeros enteros, punteros de inicio   *
  //*     y final de la lista.                           *
  //*Post: Lista de numeros ordenadas de mayor a menor   *
  //******************************************************  
  public static void quikSort(int x[],int lo,int ho)
  {
    int t, l=lo, h=ho, mid;
 
    if(ho>lo)
    {
      mid=x[(lo+ho)/2];
      while(l<h)
      {
        while((l<ho)&&(x[l]<mid))  ++l;
        while((h>lo)&&(x[h]>mid))  --h;
        if(l<=h)
        {
          //Verifica y ordena los numeros de menor a mayor  
          t    = x[l];
          x[l] = x[h];
          x[h] = t;
          ++l;
          --h;
        }
      }
      
      if(lo<h) quikSort(x,lo,h);
      if(l<ho) quikSort(x,l,ho);
    }
  }  
    
  //******************************************************
  //*              Metodo selectionSort                  *     
  //******************************************************
  //*Pre: Lista de numeros enteros                       *
  //*Post: Lista de numeros ordenadas de mayor a menor   *
  //******************************************************
  public static void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
      int min = i; 
      for (int j = i; j < nums.length; j++) {
        if (nums[j] < nums[min])
            min = j;
      }
      //Verifica y ordena los numeros de menor a mayor.
      int tmp;
      tmp = nums[i];
      nums[i] = nums[min];
      nums[min] = tmp;
      }
    }
    

    
}
